Most computers built today are of a type known as von Neumann machines. These computers require the transfer of data from memory locations, usually identified by some address or label, to a central processor unit (CPU) where some operation is applied to the data. Often, the data is moved again, either back to its original location or to another memory location. This constant movement of data is inefficient and limits the ability to make a truly parallel machine.
Lambda calculus represents another way to manipulate information to obtain desired results. In lambda calculus, special "lambda expressions" are created to describe a system which closely links data to functions. By using these lambda expressions, a universal programming machine can be constructed which produces results equivalent to those produced by von Neumann machines.
An article written by D. A. Turner ("A New Implementation Technique for Applicative Languages", Software--Practice and Experience, vol. 9, no. 1, pp. 31-49, 1979) describes a method of constructing a computing system by abstracting lambda expressions to a simpler and more powerful form called combinators. Combinators were first described by Schonfinkel and Curry in the 1930s, but Turner was the first to propose them as a way of building a computing system. Subsequently Clarke, Gladstone, MacLean and Norman described in detail computational hardware which could be built to ease the implementation of such systems. Since then, additional materials have been written about combinators including U.S. Pat. No. 4,734,848 to Yamano et al, describing parallel combinator hardware.
Combinators are an example of a graph reduction system. That is, a system where programs are represented as lists of elements which are transformed by a set of graph reduction operators. While this invention focuses on combinators because of their compactness and proven universality, the invention covers the use of any and all graph reduction systems, including those which work on strings which represent graphs.
Combinators K, S, I, B, C, and W are defined by the following functions and illustrated graphically in FIG. 1. In each case, f, g, x and y may be functions, operators, constants, or combinator expressions EQU Kxy=x EQU Sfgx=fx(gx)
Ix=x EQU Bfgx=f(gx) EQU Cfgx=(fx)g EQU Wfx=(fx)x
If programs are viewed as trees of expressions where each branch of the tree represents a separate part of the program, combinators directly alter program trees to change their structure, thereby changing the results of evaluating the tree. Combinator computing systems usually use bracket abstraction to remove references to variables; i.e., input data which changes each time the program is executed. The bracket abstraction method produces a pure combinator expression having no references to input data. Instead the combinators are applied directly to input data arranged as a graph or tree.
John Holland described the idea of using genetics as a model for solving computational problems in his 1975 monograph, Adaptation in natural and artificial systems. Holland suggested that from several sets of randomly chosen initial values, provided only that there is a way to determine if one value is "better" (as defined in some problem-specific way) than another, a solution can be obtained by combining the "genes" these values represent through a mechanism modeled after evolution.
These "genetic algorithms" provide an efficient method of converging on desired values in a large universe of possible values. If a superior value among a large number of possible values is sought, and if values can be characterized in some regular form such as a binary string, then it is possible to move quickly and efficiently toward the best solution by selecting, mating and occasionally mutating these strings from a relatively small pool of candidates providing only that it is possible to assign a value which represents the quality of a value when compared with other values.
Genetic algorithms are usually demonstrated in programs which look for the maximal or optimal value from a known measurement function such as finding function maxima or minima. For example, the "Traveling Salesperson" problem of searching for the most efficient route of travel among a very large number of possible routes is often used to demonstrate genetic algorithms.
Previous attempts at creating programs using genetic algorithm techniques have included combining genetic algorithms with rule-based systems to provide a method of building complex systems for taking actions. This may be thought of as programming by matching binary values to rules and then evolving the values to find the best combination of rules to solve the problem. This is described in Holland and Burks 1987 U.S. Pat. No. 4,697,242.
In another previous attempt, the principles of genetic algorithms were applied to programming by describing LISP programs and program pieces as potential gene elements and then evolving more complex LISP programs from these elements using the rules of genetic algorithms. This is described both in J. R. Koza's books on genetic programming and in his several genetic programming patents (U.S. Pat. Nos. 4,935,877, 5,136,686, and 5,343,554). These patents suggest that gene strings can be of variable length and that they can be related to computer expressions by one-to-one mapping of the genes to program fragments. Thus, the systems created by Koza require the mapping of gene values used in a genetic algorithm to LISP expressions in order to create new programs.